#include "network.h"
#include <iostream>                  // for std::cout
#include <utility>                   // for std::pair
#include <algorithm>                 // for std::for_each
#include <fstream>
#include <vector>
#include "global.h"

#include <boost/graph/dijkstra_shortest_paths.hpp>
#include <boost/graph/graph_traits.hpp>
#include <boost/graph/adjacency_list.hpp>

#include <boost/generator_iterator.hpp>
#include <boost/lexical_cast.hpp>
#include <boost/graph/sequential_vertex_coloring.hpp>

using namespace boost;
extern Param param;

typedef graph_traits < Graph >::vertex_descriptor vertex_descriptor;
typedef graph_traits < Graph >::edge_descriptor edge_descriptor;
typedef graph_traits < Graph >::adjacency_iterator adj_iterator;
typedef graph_traits < Graph >::out_edge_iterator out_edge_iterator;
typedef graph_traits < Graph >::degree_size_type degree_size_type;
typedef graph_traits < Graph >::vertices_size_type vertices_size_type;
typedef property_map<Graph, vertex_index_t>::type IndexMap;
typedef property_map<Graph, vertex_index_t>::const_type vertex_index_map_lc;

Network::Network():g(NULL), distanceMap(NULL), staleInformation(NULL)
{
}

Network::~Network()
{
	delete [] staleInformation;
	std::vector<int>* distanceCopy = NULL;

	int noOfVertices = num_vertices(*g);
	for (int i=0; i< noOfVertices; i++)
	{
		distanceCopy = distanceMap->find(i)->second;
		delete distanceCopy;
		distanceCopy = NULL;
	}

	delete distanceMap;
	delete g;
}


Network::Network(int noOfVertices, double density):g(NULL), distanceMap(NULL), staleInformation(NULL)
{
	//	noOfVertices = 5;
	//	density = 0.1;
	//	enum nodes { A, B, C, D, E };
	//	// below should be replaced by generating the edge array from
	//	// a random number generator based on the density parameter
	//	Edge edge_array[] = { Edge(A, E), Edge(A, C), Edge(B, D), Edge(B, E),
	//			Edge(C, B), Edge(C, D), Edge(D, E) };
	//	double weights[] = { 1, 1, 1, 1, 1, 1,  1};
	//	int num_arcs = sizeof(edge_array) / sizeof(Edge);
	//
	int numOfTies = density * (noOfVertices * (noOfVertices-1)/2);
	// int numOfTies = boost::lexical_cast<int>(numberOfTies);
	unsigned vertex1, vertex2;

	// as a degenerate case, you can set min = max for uniform_int
	boost::uniform_int<> uni_dist(1, noOfVertices);
	boost::variate_generator<base_generator_type&, boost::uniform_int<> > deg(generator, uni_dist);

	g = new Graph(noOfVertices);
	int loopCount = 0;
	int edgeCount = 0;
	while (edgeCount != numOfTies)
	{
		vertex1 = deg()-1;
		vertex2 = deg()-1;
		//cout << "random vertex1: " << vertex1 << "----random vertex2: " << vertex2 << endl;
		loopCount++;
		if (vertex1 == vertex2)
		{
			continue;
		}

		if (!isAdjacent(vertex1, vertex2))
		{
			add_edge(vertex1, vertex2, 1, *g);
			edgeCount++;
		}
	}

	distanceMap = new unorderedMap();
	staleInformation = new bool[noOfVertices];
	vector<int> *distanceList = NULL;
	for (int i=0; i<noOfVertices; i++)
	{
		staleInformation[i] = true;
		distanceList = new vector<int>(noOfVertices, 0); // initialise all elements to 0
		distanceMap->insert(std::make_pair(i, distanceList));
	}
}

Network::Network(const Network& ntwk) : g(NULL), distanceMap(NULL), staleInformation(NULL)
{
	//cout << "IN COPY CONSTRUCTOR" << endl;
	vector<int>* tempList = NULL;
	vector<int> *distanceList = NULL;

	g = new Graph(ntwk.getGraph());

	int noOfVertices = num_vertices(*g);
	const bool *staleInfoList = ntwk.getStaleInformationList();
	staleInformation = new bool[noOfVertices];
	copy (staleInfoList, staleInfoList+noOfVertices, staleInformation);

	distanceMap = new unorderedMap();
	const unorderedMap* distMap = ntwk.getUnorderedMap();

	for (int i=0; i<noOfVertices; i++)
	{
		tempList =  distMap->find(i)->second;
		distanceList = new vector<int>(noOfVertices, 0); // initialise all elements to 0
		copy (tempList->begin(), tempList->end(), distanceList->begin());

		//cout << "distanceList Contents" << " are : ";
		/*std::vector<int>::iterator it;
		for (it=distanceList->begin(); it != distanceList->end(); it++)
		{
			cout << *it << ", ";
		}
		cout << endl;

		cout << "tempList Contents are : ";
		for (it=tempList->begin(); it != tempList->end(); it++)
		{
			cout << *it << ", ";
		}
		cout << endl;*/

		distanceMap->insert(std::make_pair(i, distanceList));
	}
}

int Network::getNumEdgesOnGeodesic( int srcNode, int destNode ) const
{
	//int numOfHopsToDest = -1;
	//char name[] = "ABCDE";

	//	// conversion from 1-based indexing to 0-based indexing
	//	srcNode = srcNode - 1;
	//	destNode = destNode - 1;

	property_map<Graph, edge_weight_t>::type weightmap = get(edge_weight, *g);

	std::vector<int>* distanceCopy = distanceMap->find(srcNode)->second;
	if (staleInformation[srcNode])
	{
		//cout << "CALLING DIJSKTRA ALGORITHM" << endl;
		std::vector<vertex_descriptor> p(num_vertices(*g));
		std::vector<int> d(num_vertices(*g));
		vertex_descriptor s = vertex(srcNode, *g);
		dijkstra_shortest_paths(*g, s, predecessor_map(&p[0]).distance_map(&d[0]));

		/*cout << "Current Contents for Node " << srcNode << "is : ";
		std::vector<int>::iterator it;
		for (it=distanceCopy->begin(); it != distanceCopy->end(); it++)
		{
			cout << *it << ", ";
		}
		cout << endl;*/

		copy (d.begin(), d.end(), distanceCopy->begin());
		staleInformation[srcNode] = false;
		/*	cout << "Modified Contents for Node " << srcNode << "is : ";
		for (it=distanceCopy->begin(); it != distanceCopy->end(); it++)
		{
			cout << *it << ", ";
		}
		cout << endl;*/

		//update the entry in hashmap
		return d[(unsigned)destNode];
	}
	else
	{
		//	cout << "NOT CALLING DIJSKTRA ALGORITHM" << endl;
		return (*distanceCopy)[(unsigned)destNode];
	}
	//std::cout << "distances and parents:" << std::endl;
	//	graph_traits < Graph >::vertex_iterator vi, vend;
	//	for (tie(vi, vend) = vertices(*g); vi != vend; ++vi)
	//	{
	//		//std::cout << "distance(" << "V_" << (*vi) << ") = " << d[*vi] << ", ";
	//		//std::cout << "parent(" << "V_" << (*vi) << ") = " << "V_" << (p[*vi]) << std::endl;
	//		if (*vi == (unsigned)destNode)
	//		{
	//			numOfHopsToDest = d[*vi];
	//		}
	//	}
	//	std::cout << std::endl;
}

// adds an edge between 'src' and 'dest' nodes
void Network::add( int src, int dest )
{
	//	// conversion from 1-based indexing to 0-based indexing
	//	src = src-1;
	//	dest = dest-1;
	// Edge e(src, dest);
	//int weight = 1;
	add_edge(src, dest, 1, *g);
	int noOfVertices = num_vertices(*g);
	for (int i=0; i<noOfVertices ;i++)
	{
		staleInformation[i] = true;
	}
}

// deletes/removes the edge between 'src' and 'dest' nodes
// NOTE: 'delete' is a keyword in C++. So, could not use that for method name.
void Network::remove( int src, int dest )
{
	//	// conversion from 1-based indexing to 0-based indexing
	//	src = src-1;
	//	dest = dest-1;
	//Edge e(src, dest);
	remove_edge(src, dest, *g);
	int noOfVertices = num_vertices(*g);
	for (int i=0; i< noOfVertices;i++)
	{
		staleInformation[i] = true;
	}
}

bool Network::isAdjacent( int src, int dest ) const
{
	//	src = src-1;
	//	dest = dest-1;
	vertex_descriptor u = vertex(src, *g);
	adj_iterator adjStart, adjEnd;

	for (tie(adjStart, adjEnd) = adjacent_vertices(u, *g); adjStart != adjEnd; ++adjStart)
	{
		//cout << " *adjStart = " << *adjStart << endl;
		if (*adjStart == (unsigned)dest) {
			return true;
		}
	}
	return false;
}

void Network::dumpNetwork( const char* fileName )
{
	ofstream outputFile;
	outputFile.open(fileName);// opens the file

	outputFile << "graph ourgraph {" << endl;
	string vertexTemplate = "V_";

	graph_traits<Graph>::edge_iterator ei, ei_end;
	IndexMap index = get(vertex_index, *g);

	for (tie(ei, ei_end) = edges(*g); ei != ei_end; ++ei)
	{
		outputFile << vertexTemplate << (index[source(*ei, *g)]+1)
		<< " -- " << vertexTemplate << (index[target(*ei, *g)]+1) << ";" << endl;
	}
	outputFile << "}"<< endl;
	outputFile.close();
}

const Graph& Network::getGraph() const
{
	return *g;
}

const bool* Network::getStaleInformationList()const
{
	return staleInformation;
}

const unorderedMap* Network::getUnorderedMap()const
{
	return distanceMap;
}

NTWK_STRUCT Network::getNetworkStructure(ofstream *ofile, int &k_partite)
{
	// Star, Complete, Null, Shared Graphs
	const int NO_OF_COMPARING_GRAPHS = 4;
	double nearNessIndex[NO_OF_COMPARING_GRAPHS] = {0, 0, 0, 0};

	vector<degree_size_type> sortedInOutDegree;
	degree_size_type degree;
	vertex_descriptor u;

	graph_traits < Graph >::vertex_iterator vi, vend;
	for (tie(vi, vend) = vertices(*g); vi != vend; ++vi)
	{
		u = vertex(*vi, *g);
		degree = out_degree(u, *g);
		sortedInOutDegree.push_back(degree);
	}

	std::sort(sortedInOutDegree.begin(), sortedInOutDegree.end());
	reverse(sortedInOutDegree.begin(),sortedInOutDegree.end());

	int noofVertices = (int)num_vertices(*g);

	bool firstElement = true;
	int curDegree;
	// Dump the vector to check the result
	for (vector<degree_size_type>::const_iterator citer = sortedInOutDegree.begin();
	citer != sortedInOutDegree.end(); ++citer)
	{
		curDegree = (unsigned)(*citer);
		nearNessIndex[NS_NULL] += SQR(curDegree - 0); // pow(curDegree - 0, 2.0); // null
		if (ofile)
		{
			*ofile << (*citer) << ", ";
		}
		else
		{
			cout << (*citer) << ", ";
		}

		if (firstElement)
		{
			// cout << (*citer) << endl;
			nearNessIndex[NS_STAR] += SQR(curDegree -(noofVertices-1)); // pow((curDegree -(noofVertices-1)),2); // star
			firstElement = false;
		}
		else
		{
			nearNessIndex[NS_STAR] += SQR(curDegree - 1); //pow(curDegree - 1, 2); // star
		}
		nearNessIndex[NS_SHARED] += SQR(curDegree - 2); //pow(curDegree - 2, 2);// shared
		nearNessIndex[NS_COMPLETE] += SQR(curDegree - (noofVertices-1)); // pow(curDegree - (noofVertices-1), 2); // complete
	}
	if (ofile)
	{
		*ofile << endl;
	}
	else
	{
		cout << endl;
	}
	// cout << nearNessIndex[NS_NULL] << " " << nearNessIndex[NS_STAR] << " " << nearNessIndex[NS_SHARED] << " " << nearNessIndex[NS_COMPLETE]
	// <<endl;

	int minGraph = ( min_element(nearNessIndex, nearNessIndex + NO_OF_COMPARING_GRAPHS) - nearNessIndex);
	int check_k_part = 0;
	NTWK_STRUCT result;
    float thresh = 0.1*(noofVertices-1)*(noofVertices-1);
	switch(minGraph)
	{
	case NS_NULL:
		if (nearNessIndex[NS_NULL] == 0.0)
		{
			k_partite = 1;
			result = NS_NULL;
		}
		else if (1.0*nearNessIndex[NS_NULL]/noofVertices < thresh)
		{
			k_partite = 1;
			result = NS_NEAR_NULL;
		}
        else
        {
			check_k_part = 1;
        }
		break;

	case NS_STAR:
		if (nearNessIndex[NS_STAR] == 0.0)
		{
			k_partite = 2;
			result = NS_STAR;
		}
		else if (1.0*nearNessIndex[NS_STAR]/noofVertices < thresh)
		{
			k_partite = 2;
			result = NS_NEAR_STAR;
		} 
        else 
        {
			check_k_part = 1;
        }
		break;
	case NS_SHARED:
		if (nearNessIndex[NS_SHARED] == 0.0)
		{
			k_partite = ((noofVertices%2) == 0)? 2 : 3;
			result = NS_SHARED;
		}
		else if (1.0*nearNessIndex[NS_SHARED]/noofVertices < thresh)
        {
			k_partite = ((noofVertices%2) == 0)? 2 : 3;
			result = NS_NEAR_SHARED;
		}
        else
        {
			check_k_part = 1;
        }
		break;
	case NS_COMPLETE:
		if (nearNessIndex[NS_COMPLETE] == 0.0)
		{
			k_partite = noofVertices;
			result = NS_COMPLETE;
		}
		else if (1.0*nearNessIndex[NS_COMPLETE]/noofVertices < thresh)
		{
			k_partite = noofVertices;
			result = NS_NEAR_COMPLETE;
		}
        else
        {
			check_k_part = 1;
        }
		break;
	default:
		result = NS_TYPE_SIZE;
	}
	// cout << "Min graph" << result << endl;

	if (check_k_part) {
		std::vector<vertices_size_type> color_vec(noofVertices);
		iterator_property_map<vertices_size_type*, vertex_index_map_lc>
		color(&color_vec.front(), get(vertex_index, *g));
		vertices_size_type num_colors = sequential_vertex_coloring(*g, color);
		k_partite = (int) num_colors;
		if (k_partite < noofVertices) {
			//
			// TODO: check if its complete k-partite
			//
			if( isCompleteMultipartiteNetwork() )
				result = NS_K_PARTITE_COMPLETE;
			else
				result = NS_K_PARTITE;
		} else {
			k_partite = noofVertices;
		}
		if (ofile) {
			*ofile << "This graph is " << num_colors << " colored and is close to " << result << endl;
		}
	}

	return result;
}


// start new code - April 10, 2010
double Network::getSparsity(int src) const
{
	vertex_descriptor u = vertex(src, *g);
	adj_iterator adjStart, adjEnd, copyAdjStart, copyAdjEnd;
	int numOfDirectLinksAmongNeighbours = 0;
	int totalNeighbours = 0;

	// collect the direct links among the neighbours of vertex u
	for (tie(adjStart, adjEnd) = adjacent_vertices(u, *g); adjStart != adjEnd; ++adjStart)
	{
		totalNeighbours++;
		copyAdjStart = adjStart;
		copyAdjStart++;
		copyAdjEnd = adjEnd;

		for (; copyAdjStart != copyAdjEnd; copyAdjStart++)
		{
			if (isAdjacent((*adjStart), (*copyAdjStart)))
			{
				numOfDirectLinksAmongNeighbours++;
			}
		}
	}

	double sparsity= 0;
	if (totalNeighbours >= 2)
	{
		double val = (double(numOfDirectLinksAmongNeighbours)) / ((totalNeighbours * (totalNeighbours-1))/2.0);
		sparsity = 1-val;
	}
	else
	{
		sparsity = 0;
	}
	return sparsity;
}

/*
// is dest reachable by at max 2-hops from the src?
bool Network::isTwoHopNeighbor( int src, int dest ) const
{
    // if dest is adjacent to src, return true
    if( isAdjacent( src, dest ) )
        return true;

    // for each node k that is adjacent to src, see if dest is ajdacent to k.
    for( int i=0; i<param.N; i++ )
    {
        if( (src != i) && (isAdjacent(src, i)) && (isAdjacent(i, dest)) )
            return true;
    }

    return false;

}
 */

// return the number of neighbors of src
int Network::getNumNeighbors( int src ) const
{
	int numNeighbors = 0;

	for( int i=0; i<param.N; i++ )
	{
		if( (src != i) && (isAdjacent(src, i)) )
			numNeighbors++;
	}

	return numNeighbors;
}

bool Network::isCompleteMultipartiteNetwork()
{
	vector< vector<int>* > partitions;

	graph_traits<Graph>::vertex_iterator vi, vi_end;
	for( tie(vi, vi_end) = vertices(*g); vi != vi_end; ++vi )
	{
		bool isAdjacentToAllPartitions = true;
		for( unsigned int i=0; i<partitions.size(); i++ )
		{
			// zero-th element of the partition is our representative element of the partition
			if( isAdjacent(partitions[i]->operator[](0), *vi) == false )
			{
				// add *vi to this partition
				partitions[i]->push_back(*vi);

				isAdjacentToAllPartitions = false;
				break;
			}
		}

		// create a new partition, if this node could not be added to an existing partition
		if( isAdjacentToAllPartitions )
		{
			vector<int>* newPartition = new vector<int>;
			newPartition->push_back(*vi);
			partitions.push_back( newPartition );
		}
	}

	// check if the graph is really multi-partite. That is, in each partition,
	// there should be no edge between any pair of node
	for( unsigned int i=0; i<partitions.size(); i++ )
	{
		vector<int>* partition = partitions[i];

		for( unsigned int j = 0; j<partition->size(); j++ )
			for( unsigned int k = j+1; k<partition->size(); k++ )
				if( isAdjacent( partition->operator[](j), partition->operator[](k)) )
					return false;
	}


	// check if the graph is complete (i.e. complete multi-partite)
	for( unsigned int i=0; i<partitions.size(); i++ )
	{
		vector<int>* partition = partitions[i];

		// calculate the sum of the sizes of all partitions excepting this partition
		int sumPartitionSize = 0;
		for( unsigned int k=0; k<partitions.size(); k++ )
		{
			if( i != k )
				sumPartitionSize += partitions[k]->size();
		}


		// the degree of each node in partition i should be equal to the sum of the sizes of each of the partitions
		// excepting partition i.
		for( unsigned int j = 0; j<partition->size(); j++ )
		{
			if( getNumNeighbors(partition->operator[](j)) != sumPartitionSize )
				return false;
		}
	}


	// print the partitions
	for( unsigned int i=0; i<partitions.size(); i++ )
	{
		vector<int>* partition = partitions[i];
		printf("partition %d: ", i);
		for( unsigned int j = 0; j<partition->size(); j++ )
			printf("%d ", partition->operator[](j));
		printf("\n");
	}

	// cleanup
	for( unsigned int i=0; i<partitions.size(); i++ )
		delete partitions[i];


	return true;
}

// start new code - May 13, 2010
int Network::getNumOfDirectLinksAmongNeighbours (int src) const
{
	vertex_descriptor u = vertex(src, *g);
	adj_iterator adjStart, adjEnd, copyAdjStart, copyAdjEnd;
	int numOfDirectLinksAmongNeighbours = 0;
	int totalNeighbours = 0;

	// collect the direct links among the neighbours of vertex u
	for (tie(adjStart, adjEnd) = adjacent_vertices(u, *g); adjStart != adjEnd; ++adjStart)
	{
		totalNeighbours++;
		copyAdjStart = adjStart;
		copyAdjStart++;
		copyAdjEnd = adjEnd;

		for (; copyAdjStart != copyAdjEnd; copyAdjStart++)
		{
			if (isAdjacent((*adjStart), (*copyAdjStart)))
			{
				numOfDirectLinksAmongNeighbours++;
			}
		}
	}
	return numOfDirectLinksAmongNeighbours;
}
